package top.datacluster.basic.algorithm.leetcode.graph;

public class LeetCode200 {

    public void dfs(char[][] grid, int left, int right){
        int rowLen = grid[0].length;
        int colLen = grid.length;

        if (rowLen < 0 || colLen < 0 || left < 0 || right < 0){
            return;
        }
        if (left >= colLen || right >= rowLen){
            return;
        }
        if (grid[left][right] == '1'){
            grid[left][right] = '0';
            dfs(grid, left + 1, right);
            dfs(grid, left - 1, right);
            dfs(grid, left, right + 1);
            dfs(grid, left, right - 1);
        }


    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0){
            return 0;
        }
        int result = 0;
        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[i].length; j++){
                if (grid[i][j] == '1'){
                    dfs(grid, i, j);
                    result++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        char[][] test = new char[][]{{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
        System.out.println(new LeetCode200().numIslands(test));
    }
}
